package code;

import java.util.ArrayList;
import java.util.List;

public class Code22 {
	/*
	 * 求n对()，组成的解
	 * 思路：分治+合并
	 * (...)|(...)
	 * f(n)=()*f(n-1)+(f(1))*f(n-2)+...+(f(n-1))
	 */
    public List<String> generateParenthesis(int n) {
    	int size=n<=2?3:n+1;
    	List<String>[] table=new ArrayList[size];
    	int i;
    	for(i=0;i<size;i++){
    		table[i]=new ArrayList<String>();
    	}
    	if(n==0)
    		return table[0];
    	table[0].add("");
    	table[1].add("()");
    	table[2].add("()()");
    	table[2].add("(())");
    	
    	for(i=3;i<=n;i++){
    		for(int j=1;j<=i;j++){
    			for(int k=0;k<table[j-1].size();k++){
    				for(int l=0;l<table[i-j].size();l++){
    					StringBuilder sb=new StringBuilder(table[j-1].get(k));
    					sb.insert(0, '(');
    					sb.append(')');
    					sb.append(table[i-j].get(l));
    					table[i].add(sb.toString());
    				}
    			}
    		}
    	}
        return table[n];
    }
    public static void main(String[] args){
    	new Code22().generateParenthesis(1);
    }
}
